SuperStrict


Rem
bbdoc: Heaps
about:
Binary min and max heap data structures.

Heaps are a good implementation for a priory queue.
Heapify is O(n), insert and remove operations are O(lg n).
First is O(1).

The Compare method of objects is used for ordering.
End Rem
Module Otus.Heap


Rem
bbdoc: Abstract heap
about:
Use #TMinHeap or #TMaxHeap to create heaps.
End Rem
Type THeap Abstract
	
	Const INIT_CAP:Int = 16
	
	Method New()
		_cap = INIT_CAP
		_len = 0
		_arr = New Object[_cap]
	End Method
	
	Rem
	bbdoc: Returns the first object in the heap.
	about:
	Runs in constant time.
	End Rem
	Method First:Object()
		Assert _len, "Heap empty!"
		Return _arr[0]
	End Method
	
	Rem
	bbdoc: Creates a heap from an array
	about:
	Replaces the current contents of the heap by the array
	in O(n) time.
	End Rem
	Method Heapify(arr:Object[])
		_cap = Max(arr.length, INIT_CAP)
		_len = arr.length
		_arr = arr[.._cap]
		
		For Local p:Int = (_len - 2) Shr 1 To 0 Step -1
			_BubbleDown p
		Next
	End Method
	
	Rem
	bbdoc: Inserts a new object to the heap
	about:
	Runs in O(lg n) time.
	End Rem
	Method Insert(o:Object)
		If _cap = _len
			_cap = Max(INIT_CAP, _cap*2)
			_arr = _arr[.._cap]
		End If
		
		Local p:Int = _len
		_arr[p] = o
		_len :+ 1
		
		_BubbleUp p
	End Method
	
	Rem
	bbdoc: Removes the first object
	about:
	Special case of RemoveAt.
	End Rem
	Method RemoveFirst:Object()
		Assert _len, "Heap empty!"
		
		Local o:Object = _arr[0]
		_len :- 1
		_BubbleDown 0
		
		Return o
	End Method
	
	Rem
	bbdoc: Removes the object at position
	returns: The removed object.
	about:
	Runs in O(lg n) time.
	End Rem
	Method RemoveAt:Object(pos:Int)
		Assert _len>=pos, "Index out of range!"
		
		Local o:Object = _arr[pos]
		_len :- 1
		_arr[pos] = _arr[_len]
		
		Local op:Int = pos
		_BubbleUp pos
		If op = pos Then _BubbleDown pos
		
		Return o
	End Method
	
	' Private
	
	Field _cap:Int, _len:Int
	
	Field _arr:Object[]
	
	Method _BubbleUp(p:Int Var) Abstract
	
	Method _BubbleDown(p:Int) Abstract
	
End Type

Rem
bbdoc: Min heap
End Rem
Type TMinHeap Extends THeap
	
	Method _BubbleUp(p:Int Var)
		While p
			Local np:Int = (p-1) Shr 1
			If _arr[np].Compare( _arr[p] ) <= 0 Then Exit
			Local tmp:Object = _arr[p]
			_arr[p] = _arr[np]
			_arr[np] = tmp
			p = np
		Wend
	End Method
	
	Method _BubbleDown(p:Int)
		Local c1:Int = 2*p+1
		While c1 < _len
			Local mi:Int = p
			Local c2:Int = c1+1
			If _arr[mi].Compare( _arr[c1] ) > 0 Then mi = c1
			If c2 < _len And _arr[mi].Compare( _arr[c2] ) > 0 Then mi = c2
			
			If mi=p Exit
			
			Local tmp:Object = _arr[p]
			_arr[p] = _arr[mi]
			_arr[mi] = tmp
			
			p = mi
			c1 = 2*p+1
		Wend
	End Method
	
End Type

Rem
bbdoc: Max heap
End Rem
Type TMaxHeap Extends THeap
	
	Method _BubbleUp(p:Int Var)
		While p
			Local np:Int = (p-1) Shr 1
			If _arr[np].Compare( _arr[p] ) >= 0 Then Exit
			Local tmp:Object = _arr[p]
			_arr[p] = _arr[np]
			_arr[np] = tmp
			p = np
		Wend
	End Method
	
	Method _BubbleDown(p:Int)
		Local c1:Int = 2*p+1
		While c1 < _len
			Local mi:Int = p
			Local c2:Int = c1+1
			If _arr[mi].Compare( _arr[c1] ) < 0 Then mi = c1
			If c2 < _len And _arr[mi].Compare( _arr[c2] ) < 0 Then mi = c2
			
			If mi=p Exit
			
			Local tmp:Object = _arr[p]
			_arr[p] = _arr[mi]
			_arr[mi] = tmp
			
			p = mi
			c1 = 2*p+1
		Wend
	End Method
	
End Type
